(1)一个具有 N 个顶点的图，在去掉任意 k-1 个顶点后 (1<=K<=N) 所得的子图仍连通，

　　而去掉 K 个顶点后的图不连通则称 G 是连通的， K 称作图 G 的点连通度，记作 K(G) 试设计

(2)相应地如果至少去掉 K 条边使这个图不连通，则 K 成为图的边连通度

 

边连通度：

　　为每条边赋权值为1,然后求确定一点作为源点，枚举此点外的每个点作为汇点求最大流。

　　也可以用stoer_wagner算法求得无向图的最小割

点连通度：

　　求一个给定的无向图的点连通度，可以转换为求边连通度，怎么转换就如下所示：

 

将点连通度转化为边连通度时怎么建图呢：

1 ．构造一个网络 N

若 G 为无向图：

    (1) 原 G 图中的每个顶点 v 变成 N 网中的两个顶点 v' 和 v" ，顶点 v' 至 v" 有一条弧（有向边）连接，弧容量为 1;

    (2) 原 G 图中的每条边  e ＝ uv ，在 N 网中有两条弧 e’= u"v',e"=v"u' 与之对应， e' 弧容量为 ∞ ，  e" 弧容量为 ∞

    (3)A” (出点)为源顶点， B' （入点）为汇顶点

     注意：弧是有向边

若 G 为有向图：

    (1) 原 G 图中的每个顶点变成 N 网中的两个顶点 v’ 和 v” ，顶点 v' 至 v” 有一条弧连接，弧容量为 1

    (2) 原 G 图中的每条弧  e ＝ uv 变成一条有向轨 u'u"v'v" ，其中轨上的弧 u"v' 的容量为 ∞;

    (3)A” (出点)为源顶点， B' （入点）为汇顶点

2 ．指定一个源点 A" ，枚举汇点B'，求 A" 到 B' 的最大流 F
